\documentclass[a4paper, 12pt,TimesNewRoman]{article}
\usepackage[14pt]{extsizes}
\usepackage{cmap}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage[left=2cm,right=2cm,
top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\usepackage{indentfirst}
\usepackage{graphicx}
\graphicspath{{./images/}}
\usepackage {subcaption}
\usepackage{parskip}
\usepackage{float}
\usepackage[unicode, pdftex]{hyperref}
\author{Забродин Денис Александрович}
\title{\textbf{Деление по модулю}} 


\begin{document}
	\maketitle
	\tableofcontents\newpage
	\section{Деление по модулю}
		\subsection{Отношение эквивалентности}
			Прежде всего важно понимать, что следующие выражения эквивалентны
			\begin{itemize}
				\item $A \equiv B\ (mod\ C)$
				\item $A\ mod\ C = B\ mod\ C$
				\item $C\ |\ (A - B)$
				\item $A = B + K \cdot C$
			\end{itemize}
			Это поможет нам переключаться между \textbf{разными способами} выражения одной и той же мысли.
			
			%КАРТИНКА
			
			Убедитесь, что секторы из предыдущего примера обладают следующими свойствами.
			\begin{itemize}
				\item Все значения в одном секторе попарно связаны друг с другом.
				\item Каждое значение встречается не более чем в одном секторе (секторы взаимно непересекаются).
				\item Если собрать вместе все секторы, получится «пирог» из всех возможных целых чисел.
			\end{itemize}
		
			Пирог, куски которого обладают этими свойствами, называется \textbf{отношением эквивалентности.}\newline
			\textbf{Отношение эквивалентности} определяет, как именно следует разрезать наш пирог (то есть как мы разобъём множество всех значений) на куски (классы эквивалентности).
			
			В общем случае, отношение эквивалентности задаётся следующими тремя свойствами.
			\begin{itemize}
				\item Пирог — это все \textbf{интересующие нас значения}
				\item Кусок (или сектор) пирога — \textbf{класс эквивалентности}
				\item Принцип разрезания пирога на куски — \textbf{соотношение эквивалентности}
			\end{itemize}
			Именно поэтому сравнение по модулю C — это отношение эквивалентности. Оно разделяет множество целых чисел на C различных классов эквивалентности.
			
			Выяснив, что сравнение по модулю C — это отношение эквивалентности, давайте разберём несколько присущих ему свойств.
			Отношения эквивалентности — это отношения, обладающих следующими свойствами.
			\begin{itemize}
				\item Они \textbf{рефлексивны}, то есть A эквивалентно A.
				\item Они \textbf{симметричны}, то есть если A эквивалентно B, то B эквивалентно A.
				\item Они \textbf{транзитивны}, то есть если A эквивалентно B, а B эквивалентно C, то A эквивалентно C.
			\end{itemize}
		\subsection{Свойства сравнений}
			\textbf{Утверждение 1.4.1.} \textit{Два числа, сравнимые с третьим, сравнимы между собой.}
			
			\textbf{Утверждение 1.4.2.} \textit{Сравнения можно почленно складывать.}
			\[a^{}_{1} \equiv b^{}_{1} (mod\ m), \dots , a^{}_{k} \equiv b^{}_{k} (mod\ m)\]
			\[a^{}_{1} - b^{}_{1} = mt^{}_{1}, \dots , a^{}_{k} - b^{}_{k} = mt^{}_{k},\]
			\[a^{}_{1} + \dots + a^{}_{k} = b^{}_{1} + \dots + b^{}_{k} + m(t^{}_{1} + \dots + t^{}_{k}),\]
			\[a^{}_{1} + \dots + a^{}_{k} \equiv b^{}_{1} + \dots + b^{}_{k} (mod\ m)\]
			(1.4.17)
			чтд
			
			\textbf{Утверждение 1.4.3.} \textit{Слагаемые, стоящие в какой-либо части сравнения, можно переносить в другую, меняя знак на
			обратный.}
			
			Действительно, пользуясь утверждением 1.4.2, без ограничения общности, прибавим к сравнению (1.4.17) почленно тривиальное сравнение 
			$-bk \equiv  -bk(mod\ m)$. Получим
			\[a^{}_{1} + \dots + a^{}_{k} - b^{}_{k} \equiv b^{}_{1} + \dots + b^{}_{k} - b^{}_{k} (mod\ m)\]
			т.е
			\[a^{}_{1} + \dots + a^{}_{k} - b^{}_{k} \equiv b^{}_{1} + \dots + b^{}_{k-1}\]
			
			\textbf{Утверждение 1.4.5.} \textit{Сравнения можно почленно перемножать}
			
			Действительно, пусть a1 $\equiv$ b1(mod\ m), a2 $\equiv$ b2(mod\ m). Это
			означает, что $a_{1}$ = $b_{1}$ + $mt_{1}$, $a_{2} = b_{2} + mt_{2}$. Отсюда после
			перемножения равенств получим $a_{1}a_{2} = b_{1}b_{2} + mT, т.е. a_{1}a_{2} \equiv
			b_{1}b_{2}(mod\ m)$.
			
			\textbf{Утверждение 1.4.6.} \textit{Обе части сравнения можно возводить
			в одну и ту же степень.}
		
			\textbf{Утверждение 1.4.8.} \textit{Обе части сравнения можно разделить
			на их общий дедитель, если он взаимно прост с модулем.}
		
			Пусть
			\[a \equiv b (mod\ m), a = a_{1}d, b = b_{1}d, (m, d) = 1\]
			Тогда
			\[a_{1}d - b_{1}d = mt, (a_{1} - b_{1})d = mt\]
			Так как (m, d) = 1, то
			\[a_{1} - b_{1} = mt', a_{1} - b_{1} \equiv 0 (mod\ m), a_{1} \equiv b_{1} (mod\ m)\]
		\subsection{Дальнейшие свойства сравнений}
			\textbf{Утверждение 1.5.1.} \textit{Обе части сравнения и модуль можно
			умножить на одно и то же число.}
			
			Последовательно имеем
			
			\[a \equiv b (mod\ m), a - b = mt, m_{1}(a - b) = m_{1}mt, m_{1}a = m_{1}b + m_{1}mt\]
			
			Это значит
			\[m_{1}a \equiv m_{1}b (mod\ m_{1}m)\]
			
			\textbf{Утверждение 1.5.2.} \textit{Обе части сравнения и модуль можно
			разделить на их общий делитель.}
			
			Если
			\[a \equiv b (mod\ m), и a = a_{1}d, b = b_{1}d, m = m_{1}d,\]
			то
			\[a_{1}d = b_{1}d + m_{1}dt, a_{1} = b_{1} + m_{1}t, a_{1} \equiv b_{1} (mod\ m_{1})\]
			
			\textbf{Утверждение 1.5.3.} \textit{Если сравнение имеет место по нескольким модулям $m_{1}, m_{2}, \dots , m_{k}$, то оно имеет место и по модулю, который равен наименьшему общему кратному модулей:
			M ($m_{1}, m_{2}, \dots , m_{k}$).}
		
			В самом деле, пусть
			\[a \equiv b (mod\ m_{i}), i = 1, 2, \dots , k; тогда a - b = m_{i}t.\]
			Будучи кратным каждого из модулей, разность a - b, кратна и
			их наименьшего общего кратного.
			
			\textbf{Утверждение 1.5.4.} \textit{Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому
			делителю числа m.}
		
			\textbf{Утверждение 1.5.5.}\textit{Если одна часть сравнения и модуль делятся на какое-нибудь число, то и другая часть сравнения делится на это число.}
		
			Действительно, пусть
			\[a \equiv b (mod\ m); тогда a - b = mt\]
			Если
			\[a = a_{1}z и m = m_{1}z, то a_{1}z - m_{1}zt = b; z(a_{1} - m_{1}t) = b = zb_{1}\]		
			
			\textbf{Утверждение 1.5.6.} Если
			\[a \equiv b (mod\ m), то (a, m) = (b, m)\]
			
			Д о к а з а т е л ь с т в о. Согласно утверждению 1.5.5
			совокупность общих делителей чисел a и m совпадает с совокупностью общих делителей чисел b и m. Значит, совпадают и
			наибольшие общие делители этих чисел, что и требуется.
\end{document}
